import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 03010570
 * @date 2020/07/08
 * describe:    LeetCode : 剑指Offer 04、二维数组中的查找  https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
 */
public class LeetCode_sword_offer_04 {
    public static void main(String[] args) {
        int[][] ints = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
//        int[][] ints = {
//                {-5}
//        };
        System.out.println(findNumberIn2DArray3(ints, 5));
        System.out.println(findNumberIn2DArray3(ints, 20));
        System.out.println(findNumberIn2DArray3(ints, 15));
    }

    /**
     * 左下角计数开始
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean findNumberIn2DArray3(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int curRow = rows - 1, curColumns = 0;
        while (curRow >= 0 && curColumns < columns) {
            int temp = matrix[curRow][curColumns];
            if (temp > target) {
                curRow--;
            } else if (temp < target) {
                curColumns++;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 线性查询法：
     * 从 右上角（或左下角）开始遍历，
     * 1、当前元素 cur == target , 则返回 true
     * 2、当前元素 cur < target , cur 需要增大，cur 往下移动一行
     * 3、当前元素 cur > targer , cur 需要变小，cur 往左 移动一列
     * 时间复杂度 ： O(N+M)
     * 空间复杂度 ： O(1)
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean findNumberIn2DArray2(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int curRow = 0, curColumn = columns - 1;
        while (curRow < rows && curColumn >= 0) {
            if (matrix[curRow][curColumn] == target) {
                return true;
            } else if (matrix[curRow][curColumn] < target) {
                curRow++;
            } else {
                curColumn--;
            }
        }
        return false;
    }

    /**
     * 暴力法，两层循环解决
     * 但没有利用到二维数组排序的特性
     * 时间复杂度： O(N*M)
     * 空间复杂度：O(1)
     *
     * @param matrix
     * @param target
     * @return
     */
    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;

    }

}
